import java.util.PriorityQueue;

/**
 * 703. 数据流中的第K大元素
 * https://leetcode-cn.com/problems/kth-largest-element-in-a-stream/
 */
public class Solutions_703 {
    public static void main(String[] args) {
        int k = 3;
        int[] arr = {4, 5, 8, 2};

        KthLargest kthLargest = new KthLargest(3, arr);
        int res1 = kthLargest.add(3);  // output: 4
        System.out.println(res1);
        int res2 = kthLargest.add(5);  // output: 5
        System.out.println(res2);
        int res3 = kthLargest.add(10);  // output: 5
        System.out.println(res3);
        int res4 = kthLargest.add(9);  // output: 8
        System.out.println(res4);
        int res5 = kthLargest.add(4);  // output: 8
        System.out.println(res5);
    }
}

class KthLargest {
    // 自动将队列中的元素，升序排列
    private PriorityQueue<Integer> queue;
    private int k;

    public KthLargest(int k, int[] nums) {
        queue = new PriorityQueue<>(k);
        this.k = k;
        for (int num : nums) {
            // 调用 add 函数，添加元素到 queue 中
            // 省去了判断 queue 长度是否大于 k 并进行元素出队的操作
            add(num);
        }
    }

    public int add(int val) {
        if (queue.size() < k) {
            queue.add(val);
        } else if (queue.peek() < val) {
            // queue 长度大于等于 k 时，将队首元素与 val 比较，保留最大值
            queue.poll();
            queue.add(val);
        }
        return queue.peek();
    }
}